package com.ywgt;

import java.util.Arrays;
import java.util.Random;

/**
 * 基数排序
 */
public class RadixSort {
    public static void main(String[] args) {
       // int [] arr={125,26,266,15,0,124};
        //获取数组元素最大的长度
        int [] arr=new int[8000000];
        for (int i = 0; i < 8000000; i++) {

            arr[i]= (int) (Math.random()*8000000);
        }
        long l = System.currentTimeMillis();
        int max=arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]>max){
                max=arr[i];
            }
        }
        int maxLength=(max+"").length();
        //使用二维数组自定义桶
        int [] [] bucket=new int[10][arr.length];
        //自定义一维数组的计数器，保存对应的桶有存放了几个元素
        int [] bucketCount=new int[10];
        //最大位数为几，循环几次
        for (int i = 0,n=1; i < maxLength; i++,n*=10) {
            //存放数据 循环每个数组元素，放至到对应的桶中
            for (int j = 0; j < arr.length; j++) {
                //bucketCount[arr[j]/n%10]  取出桶内一共有多少个元素了，放在后面
                bucket[arr[j]/n%10][bucketCount[arr[j]/n%10]]=arr[j];
                //桶内数量加1
                bucketCount[arr[j]/n%10]+=1;
            }
            int index=0;//用来记录每次一个桶完成赋值后arr的下标位置
            //根据每个桶来进行循环遍历
            for (int k = 0; k < bucketCount.length; k++) {
                //如果桶内的数量不为零，进行赋值
                if (bucketCount[k]!=0){
                    //循环添加的次数为桶内已有元素的个数，从头到尾依次添加
                    for (int j = 0; j < bucketCount[k]; j++) {
                        //k是第几个桶，J是桶内的第几个元素
                        arr[index]=bucket[k][j];
                        index++;
                    }
                }
                //清空桶内的数量
                bucketCount[k]=0;
            }
        }

        long l1 = System.currentTimeMillis();
        System.out.println(l1-l);
    }
}
